/*-------------------------------------------------------------------------
 *
 * hash.h
 *	  postgres hash 访问方法实现的头文件
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/access/hash.h
 *
 * NOTES
 *		模拟 Margo Seltzer 为 unix 实现的哈希。
 *
 *-------------------------------------------------------------------------
 */
#ifndef HASH_H
#define HASH_H

#include "access/amapi.h"
#include "access/itup.h"
#include "access/sdir.h"
#include "catalog/pg_am_d.h"
#include "common/hashfn.h"
#include "lib/stringinfo.h"
#include "storage/bufmgr.h"
#include "storage/lockdefs.h"
#include "utils/hsearch.h"
#include "utils/relcache.h"

/*
 * 从哈希桶编号到桶的起始页面的物理块编号的映射。小心参数的多次评估！
 */
typedef uint32 Bucket;

#define InvalidBucket	((Bucket) 0xFFFFFFFF)

#define BUCKET_TO_BLKNO(metap,B) \
		((BlockNumber) ((B) + ((B) ? (metap)->hashm_spares[_hash_spareindex((B)+1)-1] : 0)) + 1)

/*
 * 哈希索引页面的特殊空间。
 *
 * hasho_flag 的 LH_PAGE_TYPE 位告诉我们我们正在查看的页面类型。
 * 标志字中的额外位用于更瞬态的目的。
 *
 * 要测试页面的类型，请执行 (hasho_flag & LH_PAGE_TYPE) == LH_xxx_PAGE。
 * 然而，我们确保每个使用的页面类型都有一个独特的位，以便我们可以将页面类型用 OR 连接起来，用于如 _hash_checkpage() 的允许页面类型参数。
 */
#define LH_UNUSED_PAGE			(0)
#define LH_OVERFLOW_PAGE		(1 << 0)
#define LH_BUCKET_PAGE			(1 << 1)
#define LH_BITMAP_PAGE			(1 << 2)
#define LH_META_PAGE			(1 << 3)
#define LH_BUCKET_BEING_POPULATED	(1 << 4)
#define LH_BUCKET_BEING_SPLIT	(1 << 5)
#define LH_BUCKET_NEEDS_SPLIT_CLEANUP	(1 << 6)
#define LH_PAGE_HAS_DEAD_TUPLES (1 << 7)

#define LH_PAGE_TYPE \
	(LH_OVERFLOW_PAGE | LH_BUCKET_PAGE | LH_BITMAP_PAGE | LH_META_PAGE)

/*
 * 在溢出页面中，hasho_prevblkno 存储桶链中前一个页面的块编号；在桶页面中，hasho_prevblkno 存储在最后一次分割桶时的 hashm_maxbucket 值，或者
 * 在桶创建时的值。后一种约定被用来确定缓存的元页面副本是否过旧而无法在不需要锁定或锁定元页面的情况下使用。
 *
 * hasho_nextblkno 总是桶链中下一个页面的块编号，如果没有更多这样的页面则为 InvalidBlockNumber。
 */
typedef struct HashPageOpaqueData
{
	BlockNumber hasho_prevblkno;	/* 详见上文 */
	BlockNumber hasho_nextblkno;	/* 详见上文 */
	Bucket		hasho_bucket;	/* 此 pg 所属的桶编号 */
	uint16		hasho_flag;		/* 页面类型代码 + 标志位，见上文 */
	uint16		hasho_page_id;	/* 用于哈希索引的识别 */
} HashPageOpaqueData;

typedef HashPageOpaqueData *HashPageOpaque;

#define HashPageGetOpaque(page) ((HashPageOpaque) PageGetSpecialPointer(page))

#define H_NEEDS_SPLIT_CLEANUP(opaque)	(((opaque)->hasho_flag & LH_BUCKET_NEEDS_SPLIT_CLEANUP) != 0)
#define H_BUCKET_BEING_SPLIT(opaque)	(((opaque)->hasho_flag & LH_BUCKET_BEING_SPLIT) != 0)
#define H_BUCKET_BEING_POPULATED(opaque)	(((opaque)->hasho_flag & LH_BUCKET_BEING_POPULATED) != 0)
#define H_HAS_DEAD_TUPLES(opaque)		(((opaque)->hasho_flag & LH_PAGE_HAS_DEAD_TUPLES) != 0)

/*
 * 页面 ID 是出于 pg_filedump 和类似工具的便利性，否则它们很难区分不同类型的索引页面。它应该是页面上的最后两个字节。由于对齐考虑，这在某种程度上是“免费”的。
 */
#define HASHO_PAGE_ID		0xFF80

typedef struct HashScanPosItem	/* 我们关于每个匹配的记忆 */
{
	ItemPointerData heapTid;	/* 被引用堆项的 TID */
	OffsetNumber indexOffset;	/* 索引项在页面中的位置 */
} HashScanPosItem;

typedef struct HashScanPosData
{
	Buffer		buf;			/* 如果有效，缓存被锁定 */
	BlockNumber currPage;		/* 当前哈希索引页面 */
	BlockNumber nextPage;		/* 下一个溢出页面 */
	BlockNumber prevPage;		/* prev overflow or bucket page */

	/*
	 * items数组始终按索引顺序排序（即，递增的indexoffset）。向后扫描时，从后向前填充数组是方便的，因此我们从最后一个槽开始向下填充。
	 * 因此，我们需要一个first-valid-entry和一个last-valid-entry计数器。
	 * itemIndex是一个指示最后返回给调用者的条目的游标。
	 */
	int			firstItem;		/* items[]中的第一个有效索引 */
	int			lastItem;		/* items[]中的最后一个有效索引 */
	int			itemIndex;		/* items[]中的当前索引 */

	HashScanPosItem items[MaxIndexTuplesPerPage];	/* 必须是最后一个 */
} HashScanPosData;

#define HashScanPosIsPinned(scanpos) \
( \
	AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
				!BufferIsValid((scanpos).buf)), \
	BufferIsValid((scanpos).buf) \
)

#define HashScanPosIsValid(scanpos) \
( \
	AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
				!BufferIsValid((scanpos).buf)), \
	BlockNumberIsValid((scanpos).currPage) \
)

#define HashScanPosInvalidate(scanpos) \
	do { \
		(scanpos).buf = InvalidBuffer; \
		(scanpos).currPage = InvalidBlockNumber; \
		(scanpos).nextPage = InvalidBlockNumber; \
		(scanpos).prevPage = InvalidBlockNumber; \
		(scanpos).firstItem = 0; \
		(scanpos).lastItem = 0; \
		(scanpos).itemIndex = 0; \
	} while (0)

/*
 *	HashScanOpaqueData是哈希索引扫描的私有状态。
 */
typedef struct HashScanOpaqueData
{
	/* 扫描键的哈希值，即我们寻找的哈希键 */
	uint32		hashso_sk_hash;

	/* 记住与主桶关联的缓冲区 */
	Buffer		hashso_bucket_buf;

	/*
	 * 记住与正在拆分的桶的主桶页面关联的缓冲区。这在进行拆分操作时填充正在拆分的桶的扫描中是必需的。
	 */
	Buffer		hashso_split_bucket_buf;

	/* 扫描是否在正在填充的桶上开始，由于拆分 */
	bool		hashso_buc_populated;

	/*
	 * 是否扫描正在拆分的桶？仅当 hashso_buc_populated 为 true 时，才引用此参数的值。
	 */
	bool		hashso_buc_split;
	/* 被删除项的信息，如果有的话 (killedItems 为 NULL 如果从未使用) */
	int		   *killedItems;	/* currPos.items 被杀死项的索引 */
	int			numKilled;		/* 当前存储项的数量 */

	/*
	 * 识别页面上的所有匹配项并将其保存在HashScanPosData中
	 */
	HashScanPosData currPos;	/* 当前位置信息 */
} HashScanOpaqueData;

typedef HashScanOpaqueData *HashScanOpaque;

/*
 * metapage的定义。
 */

#define HASH_METAPAGE	0		/* metapage始终是块0 */

#define HASH_MAGIC		0x6440640
#define HASH_VERSION	4

/*
 * spares[]保存当前在某个分割点之前分配的溢出页面的数量。例如，如果spares[3] = 7，那么在分割点3之前有7个溢出页面（请比较BUCKET_TO_BLKNO宏）。 
 * spares[ovflpoint]中的值会随着在索引末尾添加溢出页面而增加。一旦ovflpoint增加（即，我们实际上已经分配了属于该分割点的桶页面），
 * 先前分割点的spares数量将不再变化。
 *
 * 可以通过查看为此目的存储在专用溢出页面中的位图来找到被回收以供重用的溢出页面。这些位图页面的blknos保存在mapp[]中；
 * nmaps是当前存在的位图数量。
 *
 * spares[]的大小限制来自于这样一个事实，即不可能有超过2^32个桶与仅有的uint32哈希码。（注意：HASH_MAX_SPLITPOINTS的值即spares[]的大小
 * 被调整为适应在HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE之后的多阶段桶分配）。
 *
 * mapp[]的大小没有特别上限，除了需要适应metapage。（以8K块大小计算，1024个位图限制我们为256 GB的溢出空间...）。对于较小的块大小，
 * 我们不能使用1024个位图，因为这会导致meta页面数据越过块大小边界。因此，我们使用BLCKSZ来确定位图的最大数量。
 */
#define HASH_MAX_BITMAPS			Min(BLCKSZ / 8, 1024)

#define HASH_SPLITPOINT_PHASE_BITS	2
#define HASH_SPLITPOINT_PHASES_PER_GRP	(1 << HASH_SPLITPOINT_PHASE_BITS)
#define HASH_SPLITPOINT_PHASE_MASK		(HASH_SPLITPOINT_PHASES_PER_GRP - 1)
#define HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE	10

/* 定义哈希索引可以具有的最大分割点阶段数量 */
#define HASH_MAX_SPLITPOINT_GROUP	32
#define HASH_MAX_SPLITPOINTS \
	(((HASH_MAX_SPLITPOINT_GROUP - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) * \
	  HASH_SPLITPOINT_PHASES_PER_GRP) + \
	 HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)

typedef struct HashMetaPageData
{
	uint32		hashm_magic;	/* 哈希表的魔法数字 */
	uint32		hashm_version;	/* 版本ID */
	double		hashm_ntuples;	/* 表中存储的元组数量 */
	uint16		hashm_ffactor;	/* 目标填充因子（元组/桶） */
	uint16		hashm_bsize;	/* 索引页面大小（字节） */
	uint16		hashm_bmsize;	/* 位图数组大小（字节） - 必须是2的幂 */
	uint16		hashm_bmshift;	/* log2（位图数组大小，以位为单位） */
	uint32		hashm_maxbucket;	/* 使用中的最大桶的 ID */
	uint32		hashm_highmask; /* 用于对整个表取模的掩码 */
	uint32		hashm_lowmask;	/* 用于对表的下半部分取模的掩码 */
	uint32		hashm_ovflpoint;	/* 从哪个分割点分配溢出页面 */
	uint32		hashm_firstfree;	/* 最低编号的免费溢出页面（位号） */
	uint32		hashm_nmaps;	/* 位图页面数量 */
	RegProcedure hashm_procid;	/* 来自pg_proc的哈希函数ID */
	uint32		hashm_spares[HASH_MAX_SPLITPOINTS]; /* 每个分割点之前的备用页面 */
	BlockNumber hashm_mapp[HASH_MAX_BITMAPS];	/* 溢出位图的blknos */
} HashMetaPageData;

typedef HashMetaPageData *HashMetaPage;

typedef struct HashOptions
{
	int32		varlena_header_;	/* varlena 头部（请勿直接触摸！） */
	int			fillfactor;		/* 页面填充因子百分比（0..100） */
} HashOptions;

#define HashGetFillFactor(relation) \
	(AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
				 relation->rd_rel->relam == HASH_AM_OID), \
	 (relation)->rd_options ? \
	 ((HashOptions *) (relation)->rd_options)->fillfactor :	\
	 HASH_DEFAULT_FILLFACTOR)
#define HashGetTargetPageUsage(relation) \
	(BLCKSZ * HashGetFillFactor(relation) / 100)

/*
 * 哈希索引项的最大大小（每页只有一个是可以的）
 */
#define HashMaxItemSize(page) \
	MAXALIGN_DOWN(PageGetPageSize(page) - \
				  SizeOfPageHeaderData - \
				  sizeof(ItemIdData) - \
				  MAXALIGN(sizeof(HashPageOpaqueData)))

#define INDEX_MOVED_BY_SPLIT_MASK	INDEX_AM_RESERVED_BIT

#define HASH_MIN_FILLFACTOR			10
#define HASH_DEFAULT_FILLFACTOR		75

/*
 * 常量
 */
#define BYTE_TO_BIT				3	/* 2^3位/字节 */
#define ALL_SET					((uint32) ~0)

/*
 * 位图页面不包含元组。它们确实包含标准页面头和尾；然而，之间的内容是一个巨大的位数组。适合页面的位数显然依赖于页面大小和头尾开销。
 * 我们要求每页的位数为2的幂。
 */
#define BMPGSZ_BYTE(metap)		((metap)->hashm_bmsize)
#define BMPGSZ_BIT(metap)		((metap)->hashm_bmsize << BYTE_TO_BIT)
#define BMPG_SHIFT(metap)		((metap)->hashm_bmshift)
#define BMPG_MASK(metap)		(BMPGSZ_BIT(metap) - 1)

#define HashPageGetBitmap(page) \
	((uint32 *) PageGetContents(page))

#define HashGetMaxBitmapSize(page) \
	(PageGetPageSize((Page) page) - \
	 (MAXALIGN(SizeOfPageHeaderData) + MAXALIGN(sizeof(HashPageOpaqueData))))

#define HashPageGetMeta(page) \
	((HashMetaPage) PageGetContents(page))

/*
 * ovflpage 位图字中的位数。
 */
#define BITS_PER_MAP	32		/* uint32 中的位数 */

/* 给定位图开始地址，清除/设置第 n 位 */
#define CLRBIT(A, N)	((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
#define SETBIT(A, N)	((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
#define ISSET(A, N)		((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))

/*
 * 页面级和高级锁定模式（请参阅 README）
 */
#define HASH_READ		BUFFER_LOCK_SHARE
#define HASH_WRITE		BUFFER_LOCK_EXCLUSIVE
#define HASH_NOLOCK		(-1)

/*
 * 当声明新的操作符类时，我们要求用户为新类型的键提供
 * amproc 函数，返回一个 32 位的哈希值。我们称之为“标准”哈希函数。
 * 我们还允许一个可选的“扩展”哈希函数，它接受一个盐并
 * 返回一个 64 位的哈希值。这是强烈推荐的，但出于向后兼容的原因，可选。
 *
 * 当盐为 0 时，扩展哈希函数返回的值的低 32 位应该与
 * 标准哈希函数返回的值匹配。
 */
#define HASHSTANDARD_PROC		1
#define HASHEXTENDED_PROC		2
#define HASHOPTIONS_PROC		3
#define HASHNProcs				3


/* 公共例程 */

extern IndexBuildResult *hashbuild(Relation heap, Relation index,
								   struct IndexInfo *indexInfo);
extern void hashbuildempty(Relation index);
extern bool hashinsert(Relation rel, Datum *values, bool *isnull,
					   ItemPointer ht_ctid, Relation heapRel,
					   IndexUniqueCheck checkUnique,
					   bool indexUnchanged,
					   struct IndexInfo *indexInfo);
extern bool hashgettuple(IndexScanDesc scan, ScanDirection dir);
extern int64 hashgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
extern IndexScanDesc hashbeginscan(Relation rel, int nkeys, int norderbys);
extern void hashrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
					   ScanKey orderbys, int norderbys);
extern void hashendscan(IndexScanDesc scan);
extern IndexBulkDeleteResult *hashbulkdelete(IndexVacuumInfo *info,
											 IndexBulkDeleteResult *stats,
											 IndexBulkDeleteCallback callback,
											 void *callback_state);
extern IndexBulkDeleteResult *hashvacuumcleanup(IndexVacuumInfo *info,
												IndexBulkDeleteResult *stats);
extern bytea *hashoptions(Datum reloptions, bool validate);
extern bool hashvalidate(Oid opclassoid);
extern void hashadjustmembers(Oid opfamilyoid,
							  Oid opclassoid,
							  List *operators,
							  List *functions);

/* 私有例程 */

/* hashinsert.c */
extern void _hash_doinsert(Relation rel, IndexTuple itup, Relation heapRel);
extern OffsetNumber _hash_pgaddtup(Relation rel, Buffer buf,
								   Size itemsize, IndexTuple itup);
extern void _hash_pgaddmultitup(Relation rel, Buffer buf, IndexTuple *itups,
								OffsetNumber *itup_offsets, uint16 nitups);

/* hashovfl.c */
extern Buffer _hash_addovflpage(Relation rel, Buffer metabuf, Buffer buf, bool retain_pin);
extern BlockNumber _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer ovflbuf,
									  Buffer wbuf, IndexTuple *itups, OffsetNumber *itup_offsets,
									  Size *tups_size, uint16 nitups, BufferAccessStrategy bstrategy);
extern void _hash_initbitmapbuffer(Buffer buf, uint16 bmsize, bool initpage);
extern void _hash_squeezebucket(Relation rel,
								Bucket bucket, BlockNumber bucket_blkno,
								Buffer bucket_buf,
								BufferAccessStrategy bstrategy);
extern uint32 _hash_ovflblkno_to_bitno(HashMetaPage metap, BlockNumber ovflblkno);

/* hashpage.c */
extern Buffer _hash_getbuf(Relation rel, BlockNumber blkno,
						   int access, int flags);
extern Buffer _hash_getbuf_with_condlock_cleanup(Relation rel,
												 BlockNumber blkno, int flags);
extern HashMetaPage _hash_getcachedmetap(Relation rel, Buffer *metabuf,
										 bool force_refresh);
extern Buffer _hash_getbucketbuf_from_hashkey(Relation rel, uint32 hashkey,
											  int access,
											  HashMetaPage *cachedmetap);
extern Buffer _hash_getinitbuf(Relation rel, BlockNumber blkno);
extern void _hash_initbuf(Buffer buf, uint32 max_bucket, uint32 num_bucket,
						  uint32 flag, bool initpage);
extern Buffer _hash_getnewbuf(Relation rel, BlockNumber blkno,
							  ForkNumber forkNum);
extern Buffer _hash_getbuf_with_strategy(Relation rel, BlockNumber blkno,
										 int access, int flags,
										 BufferAccessStrategy bstrategy);
extern void _hash_relbuf(Relation rel, Buffer buf);
extern void _hash_dropbuf(Relation rel, Buffer buf);
extern void _hash_dropscanbuf(Relation rel, HashScanOpaque so);
extern uint32 _hash_init(Relation rel, double num_tuples,
						 ForkNumber forkNum);
extern void _hash_init_metabuffer(Buffer buf, double num_tuples,
								  RegProcedure procid, uint16 ffactor, bool initpage);
extern void _hash_pageinit(Page page, Size size);
extern void _hash_expandtable(Relation rel, Buffer metabuf);
extern void _hash_finish_split(Relation rel, Buffer metabuf, Buffer obuf,
							   Bucket obucket, uint32 maxbucket, uint32 highmask,
							   uint32 lowmask);

/* hashsearch.c */
extern bool _hash_next(IndexScanDesc scan, ScanDirection dir);
extern bool _hash_first(IndexScanDesc scan, ScanDirection dir);

/* hashsort.c */
typedef struct HSpool HSpool;	/* hashsort.c 中的 opaque 结构 */

extern HSpool *_h_spoolinit(Relation heap, Relation index, uint32 num_buckets);
extern void _h_spooldestroy(HSpool *hspool);
extern void _h_spool(HSpool *hspool, ItemPointer self,
					 Datum *values, bool *isnull);
extern void _h_indexbuild(HSpool *hspool, Relation heapRel);

/* hashutil.c */
extern bool _hash_checkqual(IndexScanDesc scan, IndexTuple itup);
extern uint32 _hash_datum2hashkey(Relation rel, Datum key);
extern uint32 _hash_datum2hashkey_type(Relation rel, Datum key, Oid keytype);
extern Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket,
								   uint32 highmask, uint32 lowmask);
extern uint32 _hash_spareindex(uint32 num_bucket);
extern uint32 _hash_get_totalbuckets(uint32 splitpoint_phase);
extern void _hash_checkpage(Relation rel, Buffer buf, int flags);
extern uint32 _hash_get_indextuple_hashkey(IndexTuple itup);
extern bool _hash_convert_tuple(Relation index,
								Datum *user_values, bool *user_isnull,
								Datum *index_values, bool *index_isnull);
extern OffsetNumber _hash_binsearch(Page page, uint32 hash_value);
extern OffsetNumber _hash_binsearch_last(Page page, uint32 hash_value);
extern BlockNumber _hash_get_oldblock_from_newbucket(Relation rel, Bucket new_bucket);
extern BlockNumber _hash_get_newblock_from_oldbucket(Relation rel, Bucket old_bucket);
extern Bucket _hash_get_newbucket_from_oldbucket(Relation rel, Bucket old_bucket,
												 uint32 lowmask, uint32 maxbucket);
extern void _hash_kill_items(IndexScanDesc scan);

/* hash.c */
extern void hashbucketcleanup(Relation rel, Bucket cur_bucket,
							  Buffer bucket_buf, BlockNumber bucket_blkno,
							  BufferAccessStrategy bstrategy,
							  uint32 maxbucket, uint32 highmask, uint32 lowmask,
							  double *tuples_removed, double *num_index_tuples,
							  bool split_cleanup,
							  IndexBulkDeleteCallback callback, void *callback_state);

#endif							/* HASH_H */
